#include <unordered_map>
#include <vector>
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;

// 49. 字母异位词分组
class Solution 
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        unordered_map<string, vector<string>> m;
        for(auto& s : strs)
        {
            auto tmp = s;
            sort(tmp.begin(), tmp.end());
            m[tmp].push_back(s);
        }

        vector<vector<string>> ret;
        for(auto& [_, v] : m)
        {
            ret.push_back(move(v));
        }
        return ret;
    }
};

// 128. 最长连续序列
class Solution 
{
public:
    int longestConsecutive(vector<int>& nums) 
    {
        unordered_set<int> s;
        for(int x : nums) s.insert(x);
        
        int ret = 0;
        for(int x : nums)
        {
            int cur = x;
            if(!s.count(x - 1))
            {
                while(s.count(cur + 1)) ++cur;
            }
            ret = max(ret, cur - x + 1);
        }
        return ret;
    }
};

// 移动零
class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        int n = nums.size(), left = -1, right = 0;
        while(right < n)
        {
            if(nums[right] != 0) swap(nums[++left], nums[right++]);
            else ++right;
        }
    }
};

// 盛最多水的容器
class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size() - 1, ret = 0;
        while(left < right)
        {
            int area = (right - left) * min(height[left], height[right]);
            ret = max(ret, area);
            if(height[left] < height[right]) ++left;
            else --right;
        }
        return ret;
    }
};

// 15. 三数之和
class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        for(int i = 0; i < n - 2; ++i)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            if(nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            if(nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;
            int j = i + 1, k = n - 1;
            while(j < k)
            {
                int s = nums[i] + nums[j] + nums[k];
                if(s > 0) --k;
                else if(s < 0) ++j;
                else
                {
                    ret.push_back({nums[i], nums[j], nums[k]});
                    for(++j; j < k && nums[j] == nums[j - 1]; ++j);
                    for(--k; j < k && nums[k] == nums[k + 1]; --k);
                }
            }
        }
        return ret;
    }
};

// 42. 接雨水
class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        int left = 1, right = height.size() - 2;
        int leftMax = height[0], rightMax = height.back(), ret = 0;
        while(left <= right)
        {
            if(leftMax < rightMax)
            {
                ret += max(0, leftMax - height[left]);
                leftMax = max(leftMax, height[left++]);
            }
            else
            {
                ret += max(0, rightMax - height[right]);
                rightMax = max(rightMax, height[right--]);
            }
        } 
        return ret;
    }
};

// 3. 无重复字符的最长子串
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int m[128]{}, left = 0, right = 0, n = s.size(), ret = 0;
        while(right < n)
        {
            ++m[s[right]];
            while(m[s[right]] > 1)
            {
                --m[s[left++]];
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};

// 438. 找到字符串中所有字母异位词
class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int k = p.size(), count = 0;
        int cnt1[26]{}, cnt2[26]{};
        for(int ch : p) ++cnt1[ch - 'a'];

        int left = 0, right = 0, n = s.size();
        vector<int> ret;
        while(right < n)
        {
            if(++cnt2[s[right] - 'a'] <= cnt1[s[right] - 'a']) ++count;
            while(right - left + 1 > k)
            {
                if(cnt2[s[left] - 'a']-- <= cnt1[s[left] - 'a']) --count;
                ++left;
            }
            if(count == k) ret.push_back(left);
            ++right;
        }
        return ret;
    }
};

// 560. 和为 K 的子数组
class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int, int> m;
        m[0] = 1;
        int prev = 0, ret = 0;
        for(int x : nums)
        {
            prev += x;
            if(m.count(prev - k)) ret += m[prev - k];
            ++m[prev];
        }
        return ret;
    }
};

// 239. 滑动窗口最大值
class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        deque<int> q;
        for(int i = 0; i < k; ++i)
        {
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
        }
        int n = nums.size();
        vector<int> ret = {nums[q.front()]};
        for(int i = k; i < n; ++i)
        {
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            while(q.front() + k <= i) q.pop_front();
            ret.push_back(nums[q.front()]);
        }
        return ret;
    }
};

// 76. 最小覆盖子串
class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int m = s.size(), n = t.size();
        if(m < n) return "";

        int cnt1[128]{}, cnt2[128]{}, kind = 0;
        for(char ch : t)
        {
            if(cnt1[ch]++ == 0) ++kind;
        }
        int minLen = m + 1, begin = -1, left = 0, right = 0, count = 0;
        while(right < m)
        {
            char in = s[right];
            if(++cnt2[in] == cnt1[in]) ++count;
            while(count == kind)
            {
                if(right - left + 1 < minLen)
                {
                    begin = left;
                    minLen = right - left + 1;
                }
                char out = s[left++];
                if(cnt2[out]-- == cnt1[out]) --count;
            }
            ++right;
        }
        if(begin == -1) return "";
        return s.substr(begin, minLen);
    }
};

// 53. 最大子数组和
class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n = nums.size(), ret = INT_MIN, f = 0;
        for(int i = 0; i < n; ++i)
        {
            f = max(f, 0) + nums[i];
            ret = max(ret, f);
        }
        return ret;
    }
};

// 56. 合并区间
class Solution 
{
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){
            return a[0] < b[0];
        });
        int begin = intervals[0][0], end = intervals[0][1];
        vector<vector<int>> ret;
        for(int i = 1; i < intervals.size(); ++i)
        {
            if(intervals[i][0] <= end)
                end = max(intervals[i][1], end);
            else
            {
                ret.push_back({begin, end});
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        ret.push_back({begin, end});
        return ret;
    }
};

// 189. 轮转数组
class Solution 
{
public:
    void rotate(vector<int>& nums, int k) 
    {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

// 238. 除自身以外数组的乘积
class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> ret(n);
        int leftMul = 1;
        for(int i = 0; i < n; ++i)
        {
            ret[i] = leftMul;
            leftMul *= nums[i];
        }

        int rightMul = 1;
        for(int i = n - 1; i >= 0; --i)
        {
            ret[i] *= rightMul;
            rightMul *= nums[i];
        }
        return ret;
    }
};

// 41. 缺失的第一个正数
class Solution 
{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] <= 0) nums[i] = n + 1;
        }

        for(int i = 0; i < n; ++i)
        {
            int x = abs(nums[i]);
            if(x <= n) nums[x - 1] = -abs(nums[x - 1]);
        }

        for(int i = 0; i < n; ++i)
        {
            if(nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

// 73. 矩阵置零
class Solution 
{
public:
    void setZeroes(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m), col(n);
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(!matrix[i][j])
                {
                    row[i] = col[j] = true;
                }
            }
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(row[i] || col[j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

// 54. 螺旋矩阵
class Solution 
{
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ret(m * n);
        int cur = 0, below = m - 1;
        int left = 0, right = n - 1;
        int i = 0, j = 0;
        while(true)
        {
            for(i = left; i <= right; ++i) ret[j++] = matrix[cur][i];
            if(++cur > below) break;

            for(i = cur; i <= below; ++i) ret[j++] = matrix[i][right];
            if(left > --right) break;

            for(i = right; i >= left; --i) ret[j++] = matrix[below][i];
            if(cur > --below) break;

            for(i = below; i >= cur; --i) ret[j++] = matrix[i][left];
            if(++left > right) break;
        }
        return ret;
    }
};

// 54. 螺旋矩阵
class Solution 
{
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ret(m * n);
        int i = 0, j = 0, x = 0, y = 0;
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while(j < m * n)
        {
            ret[j++] = matrix[x][y];
            matrix[x][y] = 101; // 标记已经访问过了
            int nx = x + dirs[i][0], ny = y + dirs[i][1];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] == 101)
            {
                i = (i + 1) % 4;
                nx = x + dirs[i][0], ny = y + dirs[i][1];
            }
            x = nx, y = ny;
        }
        return ret;
    }
};